// 要求自己实现一个可以使用线性效率查找最小值的栈
// 这个题目使用cpp的stl库就可以非常轻松的实现
// 要实现这一个结构,只需要实现两个栈即可: 一个存放数据,一个保存最小值
// 当栈第一次压栈,或者出现最小值的时候,就把该值往最小值栈里面压栈
// 每次出栈的时候检查,如果栈出现了目前的最小值出栈的情况的话,就出一次栈,这样子就可以保证每次去最小值栈的栈顶的时候的值都是栈的最小值了

class MinStack 
{
public:

    MinStack() {}
    
    void push(int val) 
    {

        if (ms.empty ())
        {

            min.push (val) ;
            
        }

        ms.push (val) ;

        if (!ms.empty () && val <= min.top ())
        {

            min.push (val) ;

        }
        
    }
    
    void pop() 
    {

        if (ms.top () == min.top ())
        {

            min.pop () ;

        }

        ms.pop () ;
        
    }
    
    int top() 
    {

        return ms.top () ;
        
    }
    
    int getMin() 
    {

        return min.top () ;
        
    }

private:

    stack<int> ms ;

    stack<int> min ;

} ;

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */